home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 July / macformat-026.iso / mac / Shareware City / Developers / berkeleydb1.73 / Berkeley_db / btree / bt_utils.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  6.2 KB  |  245 lines  |  [TEXT/MPS ]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_utils.c    8.2 (Berkeley) 9/7/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #if defined(macintosh) && (defined(powerc) || defined(__powerc))
  42. #include "OurMalloc.h"
  43. #endif
  44.  
  45. #include <sys/param.h>
  46.  
  47. #include <stdio.h>
  48. #include <stdlib.h>
  49. #include <string.h>
  50.  
  51. #include <db.h>
  52. #include "btree.h"
  53.  
  54. /*
  55.  * __BT_RET -- Build return key/data pair as a result of search or scan.
  56.  *
  57.  * Parameters:
  58.  *    t:    tree
  59.  *    d:    LEAF to be returned to the user.
  60.  *    key:    user's key structure (NULL if not to be filled in)
  61.  *    data:    user's data structure
  62.  *
  63.  * Returns:
  64.  *    RET_SUCCESS, RET_ERROR.
  65.  */
  66. int
  67. __bt_ret(t, e, key, data)
  68.     BTREE *t;
  69.     EPG *e;
  70.     DBT *key, *data;
  71. {
  72.     register BLEAF *bl;
  73.     register void *p;
  74.  
  75.     bl = GETBLEAF(e->page, e->index);
  76.  
  77.     /*
  78.      * We always copy big keys/data to make them contigous.  Otherwise,
  79.      * we leave the page pinned and don't copy unless the user specified
  80.      * concurrent access.
  81.      */
  82.     if (bl->flags & P_BIGDATA) {
  83.         if (__ovfl_get(t, bl->bytes + bl->ksize,
  84.             &data->size, &t->bt_dbuf, &t->bt_dbufsz))
  85.             return (RET_ERROR);
  86.         data->data = t->bt_dbuf;
  87.     } else if (ISSET(t, B_DB_LOCK)) {
  88.         /* Use +1 in case the first record retrieved is 0 length. */
  89.         if (bl->dsize + 1 > t->bt_dbufsz) {
  90.             if ((p = realloc(t->bt_dbuf, bl->dsize + 1)) == NULL)
  91.                 return (RET_ERROR);
  92.             t->bt_dbuf = p;
  93.             t->bt_dbufsz = bl->dsize + 1;
  94.         }
  95.         memmove(t->bt_dbuf, bl->bytes + bl->ksize, bl->dsize);
  96.         data->size = bl->dsize;
  97.     data->data = t->bt_dbuf;
  98.     } else {
  99.         data->size = bl->dsize;
  100.         data->data = bl->bytes + bl->ksize;
  101.     }
  102.  
  103.     if (key == NULL)
  104.         return (RET_SUCCESS);
  105.  
  106.     if (bl->flags & P_BIGKEY) {
  107.         if (__ovfl_get(t, bl->bytes,
  108.             &key->size, &t->bt_kbuf, &t->bt_kbufsz))
  109.             return (RET_ERROR);
  110.         key->data = t->bt_kbuf;
  111.     } else if (ISSET(t, B_DB_LOCK)) {
  112.         if (bl->ksize > t->bt_kbufsz) {
  113.             if ((p = realloc(t->bt_kbuf, bl->ksize)) == NULL)
  114.                 return (RET_ERROR);
  115.             t->bt_kbuf = p;
  116.             t->bt_kbufsz = bl->ksize;
  117.         }
  118.         memmove(t->bt_kbuf, bl->bytes, bl->ksize);
  119.         key->size = bl->ksize;
  120.     key->data = t->bt_kbuf;
  121.     } else {
  122.         key->size = bl->ksize;
  123.         key->data = bl->bytes;
  124.     }
  125.     return (RET_SUCCESS);
  126. }
  127.  
  128. /*
  129.  * __BT_CMP -- Compare a key to a given record.
  130.  *
  131.  * Parameters:
  132.  *    t:    tree
  133.  *    k1:    DBT pointer of first arg to comparison
  134.  *    e:    pointer to EPG for comparison
  135.  *
  136.  * Returns:
  137.  *    < 0 if k1 is < record
  138.  *    = 0 if k1 is = record
  139.  *    > 0 if k1 is > record
  140.  */
  141. int
  142. __bt_cmp(t, k1, e)
  143.     BTREE *t;
  144.     const DBT *k1;
  145.     EPG *e;
  146. {
  147.     BINTERNAL *bi;
  148.     BLEAF *bl;
  149.     DBT k2;
  150.     PAGE *h;
  151.     void *bigkey;
  152.  
  153.     /*
  154.      * The left-most key on internal pages, at any level of the tree, is
  155.      * guaranteed by the following code to be less than any user key.
  156.      * This saves us from having to update the leftmost key on an internal
  157.      * page when the user inserts a new key in the tree smaller than
  158.      * anything we've yet seen.
  159.      */
  160.     h = e->page;
  161.     if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
  162.         return (1);
  163.  
  164.     bigkey = NULL;
  165.     if (h->flags & P_BLEAF) {
  166.         bl = GETBLEAF(h, e->index);
  167.         if (bl->flags & P_BIGKEY)
  168.             bigkey = bl->bytes;
  169.         else {
  170.             k2.data = bl->bytes;
  171.             k2.size = bl->ksize;
  172.         }
  173.     } else {
  174.         bi = GETBINTERNAL(h, e->index);
  175.         if (bi->flags & P_BIGKEY)
  176.             bigkey = bi->bytes;
  177.         else {
  178.             k2.data = bi->bytes;
  179.             k2.size = bi->ksize;
  180.         }
  181.     }
  182.  
  183.     if (bigkey) {
  184.         if (__ovfl_get(t, bigkey,
  185.             &k2.size, &t->bt_dbuf, &t->bt_dbufsz))
  186.             return (RET_ERROR);
  187.         k2.data = t->bt_dbuf;
  188.     }
  189.     return ((*t->bt_cmp)(k1, &k2));
  190. }
  191.  
  192. /*
  193.  * __BT_DEFCMP -- Default comparison routine.
  194.  *
  195.  * Parameters:
  196.  *    a:    DBT #1
  197.  *    b:     DBT #2
  198.  *
  199.  * Returns:
  200.  *    < 0 if a is < b
  201.  *    = 0 if a is = b
  202.  *    > 0 if a is > b
  203.  */
  204. int
  205. __bt_defcmp(a, b)
  206.     const DBT *a, *b;
  207. {
  208.     register u_char *p1, *p2;
  209.     register int diff, len;
  210.  
  211.     len = MIN(a->size, b->size);
  212.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
  213.         if (diff = *p1 - *p2)
  214.             return (diff);
  215.     return (a->size - b->size);
  216. }
  217.  
  218. /*
  219.  * __BT_DEFPFX -- Default prefix routine.
  220.  *
  221.  * Parameters:
  222.  *    a:    DBT #1
  223.  *    b:     DBT #2
  224.  *
  225.  * Returns:
  226.  *    Number of bytes needed to distinguish b from a.
  227.  */
  228. int
  229. __bt_defpfx(a, b)
  230.     const DBT *a, *b;
  231. {
  232.     register u_char *p1, *p2;
  233.     register int len;
  234.     int cnt;
  235.  
  236.     cnt = 1;
  237.     len = MIN(a->size, b->size);
  238.     for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
  239.         if (*p1 != *p2)
  240.             return (cnt);
  241.  
  242.     /* a->size must be <= b->size, or they wouldn't be in this order. */
  243.     return (a->size < b->size ? a->size + 1 : a->size);
  244. }
  245.